package com.yiwenup.sorting._09_radix;

import com.yiwenup.sorting.base.Sort;

/**
 * 基数排序：特别适合整数排序（尤其是非负整数）
 * 时间复杂度：最好 - O(d*(n+k))；最坏 - O(d*(n+k))；平均复杂度 - (d*(n+k))【d指代最大值的位数，k指代进制】
 * 空间复杂度：O(n+K)
 * 稳定性：稳定
 **/
public class RadixSort extends Sort<Integer> {

    @Override
    protected void work() {
        // 1.找最大值，确定最大位数
        int max = array[0];
        for (int i = 0; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }

        for (int divider = 1; divider <= max; divider *= 10) {
            countingSort(divider);
        }
    }

    private void countingSort(int divider) {
        // 1. 找到最大值/最小值，确定开辟范围（0~9）
        // 2.开辟内存空间
        int[] counts = new int[10];

        // 3.统计每个元素出现的次数
        for (int i = 0; i < array.length; i++) {
            counts[array[i] / divider % 10]++;
        }

        // 4.次数累加
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }

        // 5.遍历（从后往前，可以保证稳定性）
        int[] newArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            newArray[--counts[array[i] / divider % 10]] = array[i];
        }

        // 6.有序数组覆盖
        for (int i = 0; i < newArray.length; i++) {
            array[i] = newArray[i];
        }
    }
}
